#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <map>
#include <algorithm>
#define MAX_CHAR_SIZE 27
using namespace std;
class TrieNode
{
public:
    TrieNode *child[MAX_CHAR_SIZE];
    bool isLeaf;
    TrieNode() : isLeaf(false)
    {
        for (size_t i = 0; i < MAX_CHAR_SIZE; i++)
        {
            child[i] = nullptr;
        }
    }
    ~TrieNode()
    {
        for (size_t i = 0; i < MAX_CHAR_SIZE; i++)
        {
            child[i] = nullptr;
        }
    }
};
class Trie
{
private:
    TrieNode *root;

public:
    Trie() { root = new TrieNode(); }
    ~Trie() { root = nullptr; }

    void insert(const string word)
    {
        TrieNode *p = root;
        for (char w : word)
        {
            int t = w == '#' ? 26 : (w - 'a');
            if (!p->child[t])
                p->child[t] = new TrieNode();
            p = p->child[t];
        }
        p->isLeaf = true;
    }

    bool search(const string word)
    {
        TrieNode *p = root;
        for (char w : word)
        {
            int t = w == '#' ? 26 : (w - 'a');
            if (!p->child[t])
                return false;
            p = p->child[t];
        }
        return p->isLeaf;
    }

    bool startWith(const string word)
    {
        TrieNode *p = root;
        for (auto &w : word)
        {
            int t = w - 'a';
            if (!p->child[t])
                return false;
            p = p->child[t];
        }
        return true;
    }
};

class WordFilter
{
private:
    map<string, int> dict;
    Trie trie;
    Trie prefTrie,suffTrie;

public:
    // Trie 构造后缀+前缀的插入方式
    // "apple"往Trie中插入
    // #apple
    // e#apple
    // le#apple
    // ple#apple
    // pple#apple
    // apple#apple
    // 查询时:前缀为a后缀为e
    // e#a
    WordFilter(vector<string> &words)
    {
        // w1
        for (int i = 0; i < words.size(); i++)
        {
            int m = words[i].size();
            string word = words[i];
            for (int prefixLength = 1; prefixLength <= m; prefixLength++)
            {
                for (int suffixLength = 1; suffixLength <= m; suffixLength++)
                {
                    string key = word.substr(0, prefixLength) + '#' + word.substr(m - suffixLength);
                    dict[key] = i;
                }
            }
        }

        //w2  single trie-tree
        for (string word : words)
        {
            for (int i = 0; i < words.size(); i ++ )
        {
            string s = '#' + words[i];
            trie.insert(s, i);
            for (int j = words[i].size() - 1; j >= 0; j -- )
            {
                s = words[i][j] + s;
                trie.insert(s, i);
            }
        }
        }
    }
    /**
     * @brief
     *
     * @param pref
     * @param suff
     * @return int
     */
    int fString(string pref, string suff)
    {
        string target = pref + '#' + suff;
        return dict.count(target) ? dict[target] : -1;
    }

    /**
     * @brief use trie +endwith
     *
     * @param pref
     * @param suff
     * @return int
     */
    int f(string pref, string suff)
    {
        auto endWith = [](string s, string tail) -> bool
        {
            return s.compare(s.size() - tail.size(), tail.size(), tail) == 0;
        };
        int index = -1;
        for (size_t i = 0; i < ans.size(); i++)
        {
            cout << ans[i] << endl;
            if (prefTrie.search(suff + "#" + pref))
            {
                cout << "searched:" << i << endl;
                index = (index > 0 && ans[index].length() > ans[i].length()) ? index : i;
            }
        }
        return index;
    }
};

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter* obj = new WordFilter(words);
 * int param_1 = obj->f(pref,suff);
 */
int main()
{
    // words = {"hello", "hellllo", "word", "helloword", "hellllllo"};
    vector<string> words = {"abbba", "abba"};
    WordFilter wordFilter(words);
    cout << wordFilter.fString("ab", "ba") << endl;
    system("pause");
    return 0;
}
